#include "main.h"

void _create_tree(BiTreeNode * root_pp, char * pre_order_seq, int *current_index, int num_elements) {
	if (*current_index >= num_elements){
		return;
	} else {
		root_pp->data = pre_order_seq[*current_index];
		*current_index += 1;
	}
	if (pre_order_seq[*current_index] == '#') {
		root_pp->leftChild = NULL;
		*current_index += 1;
	} else {
		root_pp->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		_create_tree(root_pp->leftChild, pre_order_seq, current_index, num_elements);
	}
	if (pre_order_seq[*current_index] == '#') {
		root_pp->rightChild = NULL;
		*current_index += 1;
	} else {
		root_pp->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		_create_tree(root_pp->rightChild, pre_order_seq, current_index, num_elements);
	}
}


void create_tree(BiTreeNode **root_pp, char *pre_order_seq, int num_elements) {
	*root_pp = (BiTreeNode *) malloc(sizeof(BiTreeNode));
	BiTreeNode *root = *root_pp;
	if (pre_order_seq[0] != '#') {
		root->data = pre_order_seq[0];
	}
	int current_index = 0;
	_create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item)) {
	if (t != NULL) {
		visit(t->data);
		pre_order_traverse(t->leftChild, visit);
		pre_order_traverse(t->rightChild, visit);
	}
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)) {
	if (t == NULL) {
		return;
	}
	in_order_traverse(t->leftChild, visit);
	visit(t->data);
	in_order_traverse(t->rightChild, visit);
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item)) {
	if (t == NULL) {
		return;
	}
	post_order_traverse(t->leftChild, visit);
	post_order_traverse(t->rightChild, visit);
	visit(t->data);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode *search(BiTreeNode *root, DataType x) {
	BiTreeNode *find = NULL;
	if (root == NULL) {
		return NULL;
	}
	if (root->data == x) {
		return root;
	} else {
		find = search(root->leftChild, x);
		if (find) {
			return find;
		}
		find = search(root->rightChild, x);
		if (find) {
			return find;
		}
	}
	return find;
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root) {
	if ((*root) != NULL) {
		if ((*root)->leftChild) {
			destroy(&(*root)->leftChild);
			(*root)->leftChild = NULL;
		}
		if ((*root)->rightChild) {
			destroy(&(*root)->rightChild);
			(*root)->rightChild = NULL;
		}
		if ((*root) != NULL) {
			free((*root));
			(*root) = NULL;
		}
	}
}


int main() {
	BiTreeNode *root;
	char x='A';
	char *pre_order_seq = "ABC##DE#G##F###";
	create_tree(&root, pre_order_seq, 15);
	printf("前序遍历为：");
	pre_order_traverse(root, visit);
	printf("\n中序遍历为：");
	in_order_traverse(root,visit);
	printf("\n后序遍历为：");
	post_order_traverse(root,visit);
	search(root,x);
	printf("\n数据元素%c在二叉树中 \n",x);
	destroy(&root);
}
